#include<iostream>
#include<vector>
using namespace std;
/*
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：
它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
解题思路：
与之前求最长重复子序列的问题类似，该题目求的公共子序列可以不连续，
dp[i][j]表示的还是nums1下标为i-1和nums2下标为j-1的最长公共子序列
并且仍然有递推公式if(nums1[i-1]==nums2[j-1])dp[i][j] = dp[i-1][j-1]+1
但是在nums1[i-1]与nums2[j-1]不相等的情况下，例如：nums1=abcde,nums2=ace;
当nums2的下标2与nums1的下标2不相等时，可以不考虑nums2的下标2元素，只看2之前的元素与nums1的最长公共子序列，
同理只看nums1下标2之前的元素与nums2的最长公共子序列并且两者取最大值
所以有else
dp[i][j] = max(dp[i][j-1],dp[i-1][j])
*/
int dp(string text1,string text2)
{
    //创建dp数组并进行初始化
    vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1));
    //遍历dp数组从第二行第二列开始进行遍历
    for(int i=1;i<=text1.size();i++)
    {
        for(int j=1;j<=text2.size();j++)
        {
            if(text1[i-1]==text2[j-1])
                dp[i][j] = dp[i-1][j-1]+1;
            else
                dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
        }
    }
    return dp[text1.size()][text2.size()];
}
int main()
{
    cout<<"enter a str1:"<<endl;
    string s1;
    cin>>s1;
    cout<<"enter a str2:"<<endl;
    string s2;
    cin>>s2;
    cout<<dp(s1,s2);
    return 0;
}